﻿using System;
using System.Collections;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Content;
using System.Threading;
using System.Collections.Generic;
using System.Diagnostics;

namespace block_explorer
{
    class Map : IDrawableComponent
    {
        // A Cell is a section of the world that could possibly hold a block
        // A Block is a Cell that contains information
        // A Sector is a collection of Cells that is Block.SIZE x Block.SIZE x Block.SIZE
        // A Map is a collection of Sectors

        Scene mScene;
        IMapBuilder mBuilder;
        JobScheduler mScheduler;
        IDictionary<SectorAddress, MapSector> mSectors;

        Texture2D mBlockTexture;
        VertexBuffer mBoundaryVBuffer;

        public IMapBuilder Builder { get { return mBuilder; } }
        public VertexBuffer SectorBoundaryVertexbuffer { get { return mBoundaryVBuffer; } }

        public bool SectorBoundaries { get; set; }

        #region Constructors
        public Map(Scene scene, IMapBuilder builder, JobScheduler scheduler)
        {
            mScene = scene;
            mBuilder = builder;
            mScheduler = scheduler;

            mSectors = new Dictionary<SectorAddress, MapSector>();
        }
        #endregion

        #region Setup methods
        public void Initialize(GraphicsDevice device, ContentManager content)
        {
            mBlockTexture = content.Load<Texture2D>("dirtstone");
            //mBlockTexture = content.Load<Texture2D>("dirt");
            //mBlockTexture = content.Load<Texture2D>("block");

            BuildSectorBoundaryBuffer(device);
        }

        private void BuildSectorBoundaryBuffer(GraphicsDevice device)
        {
            // TODO can just pass positions and do colours in shader
            VertexPositionColor[] corners = new VertexPositionColor[]
            {
                // bottom square
                new VertexPositionColor(new Vector3(0, 0, 0), Color.Red),
                new VertexPositionColor(new Vector3(0, 0, MapSector.SIZE), Color.Red),

                new VertexPositionColor(new Vector3(0, 0, MapSector.SIZE), Color.Red),
                new VertexPositionColor(new Vector3(MapSector.SIZE, 0, MapSector.SIZE), Color.Red),

                new VertexPositionColor(new Vector3(MapSector.SIZE, 0, MapSector.SIZE), Color.Red),
                new VertexPositionColor(new Vector3(MapSector.SIZE, 0, 0), Color.Red),

                new VertexPositionColor(new Vector3(MapSector.SIZE, 0, 0), Color.Red),
                new VertexPositionColor(new Vector3(0, 0, 0), Color.Red),

                // top square
                new VertexPositionColor(new Vector3(0, MapSector.SIZE, 0), Color.Red),
                new VertexPositionColor(new Vector3(0, MapSector.SIZE, MapSector.SIZE), Color.Red),

                new VertexPositionColor(new Vector3(0, MapSector.SIZE, MapSector.SIZE), Color.Red),
                new VertexPositionColor(new Vector3(MapSector.SIZE, MapSector.SIZE, MapSector.SIZE), Color.Red),

                new VertexPositionColor(new Vector3(MapSector.SIZE, MapSector.SIZE, MapSector.SIZE), Color.Red),
                new VertexPositionColor(new Vector3(MapSector.SIZE, MapSector.SIZE, 0), Color.Red),

                new VertexPositionColor(new Vector3(MapSector.SIZE, MapSector.SIZE, 0), Color.Red),
                new VertexPositionColor(new Vector3(0, MapSector.SIZE, 0), Color.Red),

                // 4 "posts"
                new VertexPositionColor(new Vector3(0, 0, 0), Color.Red),
                new VertexPositionColor(new Vector3(0, MapSector.SIZE, 0), Color.Red),

                new VertexPositionColor(new Vector3(0, 0, MapSector.SIZE), Color.Red),
                new VertexPositionColor(new Vector3(0, MapSector.SIZE, MapSector.SIZE), Color.Red),

                new VertexPositionColor(new Vector3(MapSector.SIZE, 0, MapSector.SIZE), Color.Red),
                new VertexPositionColor(new Vector3(MapSector.SIZE, MapSector.SIZE, MapSector.SIZE), Color.Red),

                new VertexPositionColor(new Vector3(MapSector.SIZE, 0, 0), Color.Red),
                new VertexPositionColor(new Vector3(MapSector.SIZE, MapSector.SIZE, 0), Color.Red),
            };

            mBoundaryVBuffer = new VertexBuffer(device, VertexPositionColor.VertexDeclaration, 24, BufferUsage.WriteOnly);
            mBoundaryVBuffer.SetData(corners);
        }

        public void Destroy()
        {
        }
        #endregion

        #region Cell/Block/Sector Access
        public MapSector GetSector(SectorAddress address)
        {
            if (mSectors.ContainsKey(address))
                return mSectors[address];
            return null;
        }

        /**
         * Returns the sector that contains the given point
         * Can return null if the sector does not exist
         */
        public MapSector GetSectorAt(Vector3 worldPosition)
        {
            SectorAddress secCoord = SectorAddress.FromWorldPosition(worldPosition);

            lock (mSectors)
            {
                if (mSectors.ContainsKey(secCoord))
                    return mSectors[secCoord];
            }

            return null;
        }

        /**
         * Returns the coords of the Cell containing this point
         */
        public static Vector3 GetCellAt(Vector3 worldPosition)
        {
            Vector3 cellPos = worldPosition / Block.SIZE;

            // because of some double to float shenannigans, if the value is
            // very close to an integer round up, otherwise round down

            if (Math.Ceiling(cellPos.X) - cellPos.X < 0.00001f)
                cellPos.X = (float)Math.Ceiling(cellPos.X);
            else
                cellPos.X = (float)Math.Floor(cellPos.X);

            if (Math.Ceiling(cellPos.Y) - cellPos.Y < 0.00001f)
                cellPos.Y = (float)Math.Ceiling(cellPos.Y);
            else
                cellPos.Y = (float)Math.Floor(cellPos.Y);

            if (Math.Ceiling(cellPos.Z) - cellPos.Z < 0.00001f)
                cellPos.Z = (float)Math.Ceiling(cellPos.Z);
            else
                cellPos.Z = (float)Math.Floor(cellPos.Z);

            return cellPos;
        }

        /**
         * Returns the block that contains the given position
         * Can return null if there is no block information at the given cell
         */
        public Block GetBlockAt(Vector3 worldPosition)
        {
            MapSector sector = GetSectorAt(worldPosition);
            if (sector != null)
                return sector.GetBlockAt(worldPosition - sector.Position);
            return null;
        }

        public void ModifyBlockAt(Vector3 worldPosition, Block.ContentType type)
        {
            MapSector sector = GetSectorAt(worldPosition);
            if (sector != null)
                sector.ModifyBlockAt(worldPosition - sector.Position, type);
        }
        #endregion

        #region Collision Tests
        // http://www.xnawiki.com/index.php/Voxel_traversal
        public IEnumerable GetCellsOnRay(Ray ray, int maxDepth)
        {
            // Implementation is based on:
            // "A Fast Voxel Traversal Algorithm for Ray Tracing"
            // John Amanatides, Andrew Woo
            // http://www.cse.yorku.ca/~amana/research/grid.pdf
            // http://www.devmaster.net/articles/raytracing_series/A%20faster%20voxel%20traversal%20algorithm%20for%20ray%20tracing.pdf
            
            // NOTES:
            // * This code assumes that the ray's position and direction are in 'cell coordinates', which means
            //   that one unit equals one cell in all directions.
            // * When the ray doesn't start within the voxel grid, calculate the first position at which the
            //   ray could enter the grid. If it never enters the grid, there is nothing more to do here.
            // * Also, it is important to test when the ray exits the voxel grid when the grid isn't infinite.
            // * The Point3D structure is a simple structure having three integer fields (X, Y and Z).

            // The cell in which the ray starts.
            // Rounds the position's X, Y and Z down to the nearest integer values.
            int x = (int)Math.Floor(ray.Position.X);
            int y = (int)Math.Floor(ray.Position.Y);
            int z = (int)Math.Floor(ray.Position.Z);

            // Determine which way we go.
            int stepX = Math.Sign(ray.Direction.X);
            int stepY = Math.Sign(ray.Direction.Y);
            int stepZ = Math.Sign(ray.Direction.Z);

            // Calculate cell boundaries. When the step (i.e. direction sign) is positive,
            // the next boundary is AFTER our current position, meaning that we have to add 1.
            // Otherwise, it is BEFORE our current position, in which case we add nothing.
            Vector3 cellBoundary = new Vector3(
                x + (stepX > 0 ? 1 : 0),
                y + (stepY > 0 ? 1 : 0),
                z + (stepZ > 0 ? 1 : 0));

            // NOTE: For the following calculations, the result will be Single.PositiveInfinity
            // when ray.Direction.X, Y or Z equals zero, which is OK. However, when the left-hand
            // value of the division also equals zero, the result is Single.NaN, which is not OK.

            // Determine how far we can travel along the ray before we hit a voxel boundary.
            Vector3 tMax = new Vector3(
                (cellBoundary.X - ray.Position.X) / ray.Direction.X,    // Boundary is a plane on the YZ axis.
                (cellBoundary.Y - ray.Position.Y) / ray.Direction.Y,    // Boundary is a plane on the XZ axis.
                (cellBoundary.Z - ray.Position.Z) / ray.Direction.Z);    // Boundary is a plane on the XY axis.
            if (ray.Direction.X == 0) tMax.X = Single.PositiveInfinity;
            if (ray.Direction.Y == 0) tMax.Y = Single.PositiveInfinity;
            if (ray.Direction.Z == 0) tMax.Z = Single.PositiveInfinity;

            // Determine how far we must travel along the ray before we have crossed a gridcell.
            Vector3 tDelta = new Vector3(
                stepX / ray.Direction.X,                    // Crossing the width of a cell.
                stepY / ray.Direction.Y,                    // Crossing the height of a cell.
                stepZ / ray.Direction.Z);                    // Crossing the depth of a cell.
            if (ray.Direction.X == 0) tDelta.X = Single.PositiveInfinity;
            if (ray.Direction.Y == 0) tDelta.Y = Single.PositiveInfinity;
            if (ray.Direction.Z == 0) tDelta.Z = Single.PositiveInfinity;

            // For each step, determine which distance to the next voxel boundary is lowest (i.e.
            // which voxel boundary is nearest) and walk that way.
            for (int i = 0; i < maxDepth; i++)
            {
                // Return it.
                yield return new Vector3(x, y, z);

                // Do the next step.
                if (tMax.X < tMax.Y && tMax.X < tMax.Z)
                {
                    // tMax.X is the lowest, an YZ cell boundary plane is nearest.
                    x += stepX;
                    tMax.X += tDelta.X;
                }
                else if (tMax.Y < tMax.Z)
                {
                    // tMax.Y is the lowest, an XZ cell boundary plane is nearest.
                    y += stepY;
                    tMax.Y += tDelta.Y;
                }
                else
                {
                    // tMax.Z is the lowest, an XY cell boundary plane is nearest.
                    z += stepZ;
                    tMax.Z += tDelta.Z;
                }
            }
        }

        // returns all the cells that touch the given bounding box
        public IEnumerable GetCellsOnBox(BoundingBox box)
        {
            // get the cell at min
            // get the cell at max
            // return all the boxes in between
            Vector3 cellAtMin = GetCellAt(box.Min);
            Vector3 cellAtMax = GetCellAt(box.Max);

            int dx = (int)(cellAtMax.X - cellAtMin.X);
            int dy = (int)(cellAtMax.Y - cellAtMin.Y);
            int dz = (int)(cellAtMax.Z - cellAtMin.Z);

            for (int z = 0; z <= dz; ++z)
            {
                for (int y = 0; y <= dy; ++y)
                {
                    for (int x = 0; x <= dx; ++x)
                    {
                        yield return cellAtMin + new Vector3(x, y, z);
                    }
                }
            }
        }

        /*
         * Intersect a ray with a given block
         * Taken from Real-Time Collision Detection. Christer Eriscon.
         * tMin is the distance along the ray of the intersection point
         * intersectionPoint is the point the intersection was made
         * returns false if there was no intersection
         */
        public bool IntersectRayBlock(Ray ray, Vector3 block, out float tMin, out Vector3 intersectPoint)
        {
            intersectPoint = new Vector3();
            tMin = 0.0f;                    // set to -Single.MaxValue to get first hit on line
            float tMax = Single.MaxValue;   // set to max distance ray can travel (for segment)

            // for all three slabs
            if (!IntersectRayBlockSlab(ray.Position.X, ray.Direction.X, block.X, ref tMin, ref tMax))
                return false;
            if (!IntersectRayBlockSlab(ray.Position.Y, ray.Direction.Y, block.Y, ref tMin, ref tMax))
                return false;
            if (!IntersectRayBlockSlab(ray.Position.Z, ray.Direction.Z, block.Z, ref tMin, ref tMax))
                return false;

            // ray intersects all 3 slabs. return point (intersectPoint) and intersection t value (tMin)
            intersectPoint = ray.Position + ray.Direction * tMin;
            return true;
        }

        /*
         * Used by IntersectRayBlock
         * Called for every axis
         */
        private bool IntersectRayBlockSlab(float rayPos, float rayDir, float blockPos, ref float tMin, ref float tMax)
        {
            if (Math.Abs(rayDir) < Single.Epsilon)
            {
                // ray is parallel to slab. no hit if origin not within slab
                if (rayPos < blockPos || rayPos > (blockPos + Block.SIZE)) return false;
            }
            else
            {
                // compute intersection t value of ray with near and far plane of slab
                float ood = 1.0f / rayDir;
                float t1 = (blockPos - rayPos) * ood;
                float t2 = ((blockPos + 1.0f) - rayPos) * ood;
                // make t1 be intersection with near plane, t2 with far plane
                if (t1 > t2)
                {
                    float temp = t2;
                    t2 = t1;
                    t1 = temp;
                }
                tMin = Math.Max(tMin, t1);
                tMax = Math.Min(tMax, t2);
                // exit with no collision as soon as slab intersection becomes empty
                if (tMin > tMax) return false;
            }
            return true;
        }

        /*
         * Intersect a line segment with a given block
         * Taken from Real-Time Collision Detection. Christer Eriscon.
         * returns false if there was no intersection
         */
        public bool IntersectSegmentBlock(Vector3 p0, Vector3 p1, Vector3 block)
        {
            float halfBlockSize = Block.SIZE / 2.0f;
            Vector3 e = new Vector3(halfBlockSize, halfBlockSize, halfBlockSize);   // block halflength extents
            Vector3 c = block + e;          // Block center-point
            Vector3 m = (p0 + p1) * 0.5f;   // segment midpoint
            Vector3 d = p1 - m;             // segment halflength vector
            m = m - c;                      // translate box and segment to origin

            // try world coordinate axes as separating axes
            float adx = Math.Abs(d.X);
            if (Math.Abs(m.X) > e.X + adx) return false;
            float ady = Math.Abs(d.Y);
            if (Math.Abs(m.Y) > e.Y + ady) return false;
            float adz = Math.Abs(d.Z);
            if (Math.Abs(m.Z) > e.Z + adz) return false;

            // add in an epsilon term to counteract arithmetic errors when segment is
            // (near) parallel to a coordinate axis (see text for detail)
            adx += Single.Epsilon;
            ady += Single.Epsilon;
            adz += Single.Epsilon;

            // try cross products of segment direction vector with coordinate axes
            if (Math.Abs(m.Y * d.Z - m.Z * d.Y) > e.Y * adz + e.Z * ady) return false;
            if (Math.Abs(m.Z * d.X - m.X * d.Z) > e.X * adz + e.Z * adx) return false;
            if (Math.Abs(m.X * d.Y - m.Y * d.X) > e.X * ady + e.Y * adx) return false;

            // no separating axis found; segment must be overlapping block
            return true;
        }

        public bool IntersectBoxBlock(BoundingBox bbox, Vector3 block)
        {
            BoundingBox blockBox = new BoundingBox(block, block + new Vector3(Block.SIZE, Block.SIZE, Block.SIZE));
            if (bbox.Max.X < blockBox.Min.X || bbox.Min.X > blockBox.Max.X) return false;
            if (bbox.Max.Y < blockBox.Min.Y || bbox.Min.Y > blockBox.Max.Y) return false;
            if (bbox.Max.Z < blockBox.Min.Z || bbox.Min.Z > blockBox.Max.Z) return false;
            return true;
        }

        public bool IntersectMovingBlock(BoundingBox bbox, Vector3 vel, Vector3 block, out float tFirst, out float tLast, out Vector3 collisionNormal)
        {
            // exit early if the box is initially intersecting with the block
            //if (IntersectBoxBlock(bbox, block))
            //{
            //    tFirst = tLast = 0.0f;
            //    collisionNormal = Vector3.Zero;
            //    return true;
            //}

            // initialise times of first and last contact
            tFirst = 0.0f;
            tLast = 1.0f;

            BoundingBox a = new BoundingBox(block, block + new Vector3(Block.SIZE, Block.SIZE, Block.SIZE));
            BoundingBox b = bbox;

            collisionNormal = new Vector3();
            float axisTFirst = 0.0f;
            float axisTLast = 1.0f;
            Vector3 tFirstTimes = new Vector3(0, 0, 0);
            Vector3 tLastTimes = new Vector3(Single.MaxValue, Single.MaxValue, Single.MaxValue);

            if (IntersectMovingBlockAxis(a.Min.X, a.Max.X, b.Min.X, b.Max.X, vel.X, out axisTFirst, out axisTLast))
            {
                tFirstTimes.X = axisTFirst;
                tLastTimes.X = axisTLast;
                tFirst = Math.Max(axisTFirst, tFirst);
                tLast = Math.Min(axisTLast, tLast);
            }
            else
                return false;

            if (IntersectMovingBlockAxis(a.Min.Y, a.Max.Y, b.Min.Y, b.Max.Y, vel.Y, out axisTFirst, out axisTLast))
            {
                tFirstTimes.Y = axisTFirst;
                tLastTimes.Y = axisTLast;
                tFirst = Math.Max(axisTFirst, tFirst);
                tLast = Math.Min(axisTLast, tLast);
            }
            else
                return false;

            if (IntersectMovingBlockAxis(a.Min.Z, a.Max.Z, b.Min.Z, b.Max.Z, vel.Z, out axisTFirst, out axisTLast))
            {
                tFirstTimes.Z = axisTFirst;
                tLastTimes.Z = axisTLast;
                tFirst = Math.Max(axisTFirst, tFirst);
                tLast = Math.Min(axisTLast, tLast);
            }
            else
                return false;

            // no overlap possible if time of first contact occurs after time of last contact
            if (tFirst > tLast) return false;

            if (tFirstTimes.X <= Single.Epsilon &&
                tFirstTimes.Y <= Single.Epsilon &&
                tFirstTimes.Z <= Single.Epsilon)
            {
                // already touching or intersecting
                // the normal will be the smallest overlapping axis
                Vector3 aCenter = Util.BoundingBoxEx.Center(a);
                Vector3 bCenter = Util.BoundingBoxEx.Center(b);
                BoundingBox overlap = Util.BoundingBoxEx.Union(a, b);
                Vector3 overlapCenter = Util.BoundingBoxEx.Center(overlap) - aCenter;
                Vector3 overlapDimensions = Util.BoundingBoxEx.Dimensions(overlap);

                if (Math.Abs(overlapCenter.X) > Math.Abs(overlapCenter.Y) && Math.Abs(overlapCenter.X) > Math.Abs(overlapCenter.Z))
                {
                    if (vel.X * overlapCenter.X >= 0) return false;
                    if (overlapDimensions.Y <= Single.Epsilon ||
                        overlapDimensions.Z <= Single.Epsilon) return false;
                    collisionNormal = new Vector3(Math.Sign(overlapCenter.X), 0, 0);
                }
                else if (Math.Abs(overlapCenter.Y) > Math.Abs(overlapCenter.Z))
                {
                    if (vel.Y * overlapCenter.Y >= 0) return false;
                    if (overlapDimensions.X <= Single.Epsilon ||
                        overlapDimensions.Z <= Single.Epsilon) return false;
                    collisionNormal = new Vector3(0, Math.Sign(overlapCenter.Y), 0);
                }
                else
                {
                    if (vel.Z * overlapCenter.Z >= 0) return false;
                    if (overlapDimensions.X <= Single.Epsilon ||
                        overlapDimensions.Y <= Single.Epsilon) return false;
                    collisionNormal = new Vector3(0, 0, Math.Sign(overlapCenter.Z));
                }
            }
            else
            {
                Vector3 aCenter = Util.BoundingBoxEx.Center(a);
                Vector3 bCenter = Util.BoundingBoxEx.Center(b);
                BoundingBox overlap = Util.BoundingBoxEx.Union(a, b);
                Vector3 overlapDimensions = Util.BoundingBoxEx.Dimensions(overlap);
                
                if (tFirstTimes.X > tFirstTimes.Y && tFirstTimes.X > tFirstTimes.Z)
                {
                    if (overlapDimensions.Y <= Single.Epsilon ||
                        overlapDimensions.Z <= Single.Epsilon) return false;
                    collisionNormal = new Vector3(-Math.Sign(vel.X), 0, 0);
                }
                else if (tFirstTimes.Y > tFirstTimes.Z)
                {
                    if (overlapDimensions.X <= Single.Epsilon ||
                        overlapDimensions.Z <= Single.Epsilon) return false;
                    collisionNormal = new Vector3(0, -Math.Sign(vel.Y), 0);
                }
                else
                {
                    if (overlapDimensions.X <= Single.Epsilon ||
                        overlapDimensions.Y <= Single.Epsilon) return false;
                    collisionNormal = new Vector3(0, 0, -Math.Sign(vel.Z));
                }
            }

            return true;
        }

        private bool IntersectMovingBlockAxis(float aMin, float aMax, float bMin, float bMax, float vel, out float tFirst, out float tLast)
        {
            tFirst = 0.0f;
            tLast = 1.0f;

            // for each axis, determine times of first and last contact, if any
            //if (vel < 0.0f)
            //{
            //    if (bMax < aMin) return false; // nonintersecting and moving apart
            //    if (aMax < bMin) tFirst = Math.Max((aMax - bMin) / vel, tFirst);
            //    if (bMax > aMin) tLast = Math.Min((aMin - bMax) / vel, tLast);
            //}
            //else if (vel > 0.0f)
            //{
            //    if (bMin > aMax) return false; // nonintersecting and moving apart
            //    if (bMax < aMin) tFirst = Math.Max((aMin - bMax) / vel, tFirst);
            //    if (aMax > bMin) tLast = Math.Min((aMax - bMin) / vel, tLast);
            //}
            //else
            //    return false;

            if (vel < 0.0f)
            {
                if (bMax < aMin) return false; // nonintersecting and moving apart
                if (aMax < bMin) tFirst = (aMax - bMin) / vel;
                if (bMax > aMin) tLast = (aMin - bMax) / vel;
            }
            else if (vel > 0.0f)
            {
                if (bMin > aMax) return false; // nonintersecting and moving apart
                if (bMax < aMin) tFirst = (aMin - bMax) / vel;
                if (aMax > bMin) tLast = (aMax - bMin) / vel;
            }

            return true;
        }

        public bool IntersectLineSegment(Vector3 p0, Vector3 p1, out Vector3 cell, out Vector3 t)
        {
            cell = Vector3.Zero;
            t = Vector3.Zero;

            Vector3 direction = p1 - p0;
            int d = (int)((Math.Abs(direction.X) + Math.Abs(direction.Y) + Math.Abs(direction.Z)) / Block.SIZE) + 2;

            Ray ray = new Ray(p0, direction);
            foreach(Vector3 c in GetCellsOnRay(ray, d))
            {
                cell = c;
                Block block = GetBlockAt(cell);
                // first test if the block is solid
                if (block == null || block.Content == Block.ContentType.AIR)
                    continue;
                // test if the block is within the segment
                // additionally, if this fails we could probably assume we've gone
                // beyond the bounds of the segment and can fail the whole method
                if (!IntersectSegmentBlock(p0, p1, cell))
                    continue;
                // now find the intersection point
                float tMin;
                if (IntersectRayBlock(ray, cell, out tMin, out t))
                    return true;
            }

            return false;
        }

        private class FacePlaneT { public Plane plane; public float? t; }

        public Vector3 GetFaceNormal(Vector3 c, Ray r)
        {
            List<FacePlaneT> results = new List<FacePlaneT>();

            // generate a plane for each cell face. front back left right top bottom
            // and calculate t for each against the ray
            for (int i = 0; i < 6; ++i)
                results.Add(new FacePlaneT());
            results[0].plane = new Plane(new Vector3(c.X, c.Y, c.Z + 1), new Vector3(c.X + 1, c.Y, c.Z + 1), new Vector3(c.X + 1, c.Y + 1, c.Z + 1));
            results[0].t = r.Intersects(results[0].plane);
            results[1].plane = new Plane(new Vector3(c.X, c.Y, c.Z), new Vector3(c.X, c.Y + 1, c.Z), new Vector3(c.X + 1, c.Y + 1, c.Z));
            results[1].t = r.Intersects(results[1].plane);
            results[2].plane = new Plane(new Vector3(c.X, c.Y, c.Z), new Vector3(c.X, c.Y, c.Z + 1), new Vector3(c.X, c.Y + 1, c.Z + 1));
            results[2].t = r.Intersects(results[2].plane);
            results[3].plane = new Plane(new Vector3(c.X + 1, c.Y, c.Z), new Vector3(c.X + 1, c.Y + 1, c.Z), new Vector3(c.X + 1, c.Y + 1, c.Z + 1));
            results[3].t = r.Intersects(results[3].plane);
            results[4].plane = new Plane(new Vector3(c.X, c.Y + 1, c.Z), new Vector3(c.X, c.Y + 1, c.Z + 1), new Vector3(c.X + 1, c.Y + 1, c.Z + 1));
            results[4].t = r.Intersects(results[4].plane);
            results[5].plane = new Plane(new Vector3(c.X, c.Y, c.Z), new Vector3(c.X + 1, c.Y, c.Z), new Vector3(c.X + 1, c.Y, c.Z + 1));
            results[5].t = r.Intersects(results[5].plane);

            // sort so the smallest t is in the front
            results.Sort(delegate(FacePlaneT fnt1, FacePlaneT fnt2)
            {
                if (fnt1.t == null && fnt1.t == null) return 0;
                else if (fnt1.t == null) return 1;
                else if (fnt2.t == null) return -1;

                if (fnt1.t == fnt2.t) return 0;
                else if (fnt1.t < fnt2.t) return -1;
                else return 1;

                //return fnt1.t == fnt2.t ? 0 : fnt1.t < fnt2.t ? -1 : 1;
            });

            // look for the first t value that is within the bounds of a cell face
            foreach (FacePlaneT fnt in results)
            {
                Vector3? point = r.Position + r.Direction * fnt.t;

                if (point == null)
                    continue;

                if (Math.Abs(fnt.plane.Normal.X) == 1)
                {
                    if (point.Value.Y < c.Y || point.Value.Y > (c.Y + 1.0f))
                        continue;
                    if (point.Value.Z < c.Z || point.Value.Z > (c.Z + 1.0f))
                        continue;
                }
                else if (Math.Abs(fnt.plane.Normal.Y) == 1)
                {
                    if (point.Value.X < c.X || point.Value.X > (c.X + 1.0f))
                        continue;
                    if (point.Value.Z < c.Z || point.Value.Z > (c.Z + 1.0f))
                        continue;
                }
                else
                {
                    if (point.Value.X < c.X || point.Value.X > (c.X + 1.0f))
                        continue;
                    if (point.Value.Y < c.Y || point.Value.Y > (c.Y + 1.0f))
                        continue;
                }

                return fnt.plane.Normal;
            }

            return Vector3.Zero;
        }
        #endregion

        #region Sector caching methods
        private void RefreshSectorCache(SceneCamera camera)
        {
            // determine the sector address for the camera
            SectorAddress startAddress = SectorAddress.FromWorldPosition(camera.Position);

            // remove sectors too far from the camera
            ClearFarCachedSectors(startAddress);

            const int cacheSizeXZ = 15;
            const int cacheSizeY = 15;
            SectorAddress minCacheAddress = new SectorAddress(startAddress.X - cacheSizeXZ / 2, startAddress.Y - cacheSizeY / 2, startAddress.Z - cacheSizeXZ / 2);

            for (int x = 0; x < cacheSizeXZ; ++x)
            {
                for (int z = 0; z < cacheSizeXZ; ++z)
                {
                    for (int y = 0; y < cacheSizeY; ++y)
                    {
                        SectorAddress address = minCacheAddress + new SectorAddress(x, y, z);
                        TryCacheSector(address);
                    }
                }
            }
        }

        private void TryCacheSector(SectorAddress address)
        {
            // check if we've already got a cached sector
            if (mSectors.ContainsKey(address))
                return;

            MapSector newSector = new MapSector(this);
            mSectors[address] = newSector; // add to the cache immediately because the build process might try to access it
            newSector.Address = address;    // let the sector know what address it has
            if (address.Y == 4) newSector.SkySector = true;
            mScheduler.QueueBuild(newSector);
        }

        // removes sectors thar are too far from the given sector
        private void ClearFarCachedSectors(SectorAddress homeSector)
        {
            const int maxCacheSizeXY = 16;
            const int maxCacheSizeY = 16;

            List<SectorAddress> deadList = new List<SectorAddress>();

            foreach (var address in mSectors.Keys)
            {
                int dX = homeSector.X - address.X;
                int dY = homeSector.Y - address.Y;
                int dZ = homeSector.Z - address.Z;

                //SectorAddress diff = homeSector - address;
                if (Math.Abs(dX) >= Math.Ceiling(maxCacheSizeXY / 2.0f)
                    || Math.Abs(dY) >= Math.Ceiling(maxCacheSizeY / 2.0f)
                    || Math.Abs(dZ) >= Math.Ceiling(maxCacheSizeXY / 2.0f))
                {
                    deadList.Add(address);
                }
            }

            lock (mSectors)
            {
                foreach (var address in deadList)
                {
                    mSectors.Remove(address);
                }
            }
        }
        #endregion

        #region Update methods
        public void Update(GameTime gameTime)
        {
            RefreshSectorCache(mScene.SelectedCamera);
            UpdateVisibility(mScene.SelectedCamera);

            foreach (var kvp in mSectors)
            {
                kvp.Value.Update(gameTime);

                if (kvp.Value.NeedsLightsRefresh || kvp.Value.NeedsMeshRefresh || kvp.Value.NeedsFullLightsRefresh)
                    mScheduler.QueueBuild(kvp.Value);
            }
        }

        private void UpdateVisibility(Camera camera)
        {
            foreach (var kvp in mSectors)
            {
                if (camera.Frustum.Contains(kvp.Value.Bounds) != ContainmentType.Disjoint)
                    kvp.Value.Visible = true;
                else
                    kvp.Value.Visible = false;
            }
        }
        #endregion

        #region Draw Methods
        public void Draw(GraphicsDevice device, Camera camera, Shaders.WorldShader effect)
        {
            device.BlendState = BlendState.Opaque;
            device.DepthStencilState = DepthStencilState.Default;

            effect.Texture = mBlockTexture;

            foreach (var sector in mSectors.Values)
            {
                if (sector.Built)
                {
                    if (camera.Frustum.Contains(sector.Bounds) != ContainmentType.Disjoint)
                    {
                        Matrix m = Matrix.CreateTranslation(sector.Position);
                        effect.World = m;

                        foreach (EffectPass pass in effect.Passes)
                        {
                            pass.Apply();
                            sector.Draw(device);
                        }
                    }

                }
            }
        }

        public void Draw2D(GraphicsDevice device, Camera camera, Shaders.Render2DEffect effect)
        {
            if (SectorBoundaries)
                DrawSectorBoundaries(device, camera, effect);
        }

        private void DrawSectorBoundaries(GraphicsDevice device, Camera camera, Shaders.Render2DEffect effect)
        {
            device.BlendState = BlendState.Opaque;
            device.DepthStencilState = DepthStencilState.Default;

            foreach (var sector in mSectors.Values)
            {
                if (sector.Built)
                {
                    if (camera.Frustum.Contains(sector.Bounds) != ContainmentType.Disjoint)
                    {
                        Matrix m = Matrix.CreateTranslation(sector.Position);
                        effect.World = m;

                        foreach (EffectPass pass in effect.Passes)
                        {
                            pass.Apply();
                            sector.Draw2D(device);
                        }
                    }

                }
            }
        }

        #endregion
    }
}
